/**
 * 广义表(Generalized List): 又称列表, 是一种非线性结构
 * 
 * 广义表是线性表的推广, 线性表是广义表的特例; 线性表中的表元素是一个原子, 表示不可再分的特性, 而广义表中则放松了对表元素是原子的限制
 * 
 * 广义表中的表元素可以是一个原子, 也可以是一个子表
 * 
 * 定义: 广义表是一个由 n(n>=0) 个a1, a2, a3, ..., an 个元素组成的有限序列
 * 
 * 记作: L = (a1, a2, a3, ..., an); 
 *    1. 其中表元素 ai 可以是原子也可以是子表; 
 *    2. L为广义表的名字
 *    3. n为广义表的长度
 *    4. 深度: 广义表嵌套的最大层数, 简单来说就是所有原子元素嵌套的括号层数最多的
 * 
 * 注意:
 * 1. 广义表通常使用圆括号括起来, 用逗号分隔其中的元素
 * 2. 为了区分原子和广义表, 书写时使用大写字母表示广义表, 小写字母表示原子
 * 3. 若广义表Ls非空(n>=1), 则 a1 为表头, 其余元素 (a2, a3, ..., an) 称为Ls的表尾
 * 4. 广义表是递归定义的
 * 
 * 广义表的储存方式有两种: 头尾链表储存结构和扩展线性储存
 * 
 * 参考地址: https://blog.csdn.net/White100/article/details/115055005
 * 
 */
#ifndef _GLIST_H_
#define _GLIST_H_

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;
typedef int ElemType;
typedef int AtomType;

// 1. 扩展线性储存
// 元素类型标志
// typedef enum {
//   // 0 原子,
//   ATOM,
//   // 1 子表
//   LIST
// } ElemTag;
// typedef struct GNode {
//   ElemTag tag;
//   union
//   {
//     AtomType atom;
//     struct GNode *hp;
//   } ptr;
//   struct GNode *tp;
// } GNode, *GList;


// 2. 头尾链表储存结构
// 元素类型标志
typedef enum {
  // 0 原子,
  ATOM,
  // 1 子表
  LIST
} ElemTag;
typedef struct GNode {
  // 元素标志, 区分是原子还是子表
  ElemTag tag;
  union {
    // tag==ATOM时, atom存放原子结点值
    AtomType atom;
    // tag==LIST时, 表示是子表
    struct {
      // 指向表头
      struct GNode *hp;
      // 指向表尾
      struct GNode *tp;
    } ptr;
  } elem;
} GNode, *GList;

// 创建一个空的广义表
void InitGList(GList *list);

// 创建一个长度为 2 的广义表, 表头是原子结点, 值为 ch
void CreateGList(GList *list, char ch);

// 创建原子结点
GNode *MakeAtom(AtomType e);

// 判断广义表是否为空
Status GListIsEmpty(GList list);

// 在广义表的表头插入 head 元素
Status InsertHead(GList *list, GNode *head);

// 广义表的长度
int GListLength(GList list);

// 在广义表的表尾添加新的结点
Status InsertTail(GList *list, GNode *tail);

// 由广义表 L 复制为广义表 T
int CopyGList(GList *t, GList l);

// 获取表头
GNode* GetHead(GList list);

// 获取表尾（第一层的尾节点）
GNode* GetTail(GList list);

// 获取表尾（最底层的尾节点）
GNode* GetTailLast(GList list);

// 删除一个广义表L的表头，把删除的表头保存在p中
Status DeleteHead(GList *list, GNode *p);

// 广义表的深度
int GListDepth(GList list);

// 遍历
void visit(AtomType e);

// 广义表的遍历
Status GListTraverse(GList *l, void(*visitP)(AtomType e));

#endif